#include <iostream>
#define maxsize 100
using namespace std;
int a[maxsize];
int n;
int Partion(int left,int right)
{
    int i=left,j=right;
    int temp=a[left];
    //退出的条件是i和j相遇
    while(i<j)
    {
        //找到第一个比它小的
        while(i<j&&a[j]>=temp)
        {
            j--;
        }
        a[i]=a[j];
        //找到第一个比它大的
        while (i<j&&a[i]<=temp)
        {
            i++;
        }
        a[j]=a[i];
    }
    a[i]=temp;
    return i;

}
void QuickSort(int left,int right,int k)
{
    if(left>=right)
        return;
    int mid=Partion(left,right);
    if(mid==k)
    {
        cout<<"第k个元素为"<<a[k];
        return;
    }


    QuickSort(left,mid-1,k);

    QuickSort(mid+1,right, k);

}
void print(int a[])
{
    for(int i=0;i<n;++i)
        cout<<a[i]<<" ";
    cout<<endl;
}
int main() {
    cin>>n;
    srand(time(0));
    for(int i=0;i<n;++i)
    {
        a[i]=rand()%(100)+1;
    }
    print(a);
    QuickSort(0,n-1,2);
//    print(a);



    return 0;
}
